Exercise 1 (Homework 7).
(polynomial time,
exponential time)
Travelling salesperson problem
Suppose that we are given an instance of the Travelling Salesperson Problem (\mathtt{TSP}) with n cities and distances d_{ij}. For each subset S of the cities excluding city 1, and for each j \in S, define c[S,j] to be the shortest path that starts from city 1, visits all cities in S and ends up in city j.
- Give an algorithm that calculates c[S,j] by dynamic programming, that is, progressing from smaller to larger sets S and using a recurrent definition of c[S,j]. Show that this algorithm solves the \mathtt{TSP} in time O(n^2 2^n). What are the space requirements of the algorithm?
- Suppose we wish to find the shortest (in the sense of sum of weights) path from 1 to n, not necessarily visiting all cities. Argue why this problem can be solved in polynomial time.